package com.lun.medium;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class AddOneRowToTree {
	
	//方法一：BFS
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
    	if(depth == 1) {
    		return new TreeNode(val, root, null);
    	}
		LinkedList<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		int level = 1;
		
		while(!queue.isEmpty()) {
			
			++level;
			for(int size = queue.size(); size > 0; size--) {
    			TreeNode node = queue.poll();
    			
    			if(level == depth) {
    				node.left = new TreeNode(val, node.left, null);
    				node.right = new TreeNode(val, null, node.right);
    			}else {
    				if(node.left != null)
    					queue.offer(node.left);
    				
    				if(node.right != null)
    					queue.offer(node.right);
    			}
			}
		}
		
		return root;
    }
    
    //方法二：DFS
    public TreeNode addOneRow2(TreeNode root, int val, int depth) {
    	if(depth == 1) {
    		return new TreeNode(val, root, null);
    	}
		addOneRow2(root, val, depth, 1);
		return root;
    }
    
    private void addOneRow2(TreeNode node, int val, int depth, int level) {
    	if(node == null) return;
    	
    	if(++level == depth) {
    		node.left = new TreeNode(val, node.left, null);
			node.right = new TreeNode(val, null, node.right);
			return;
    	}
    	addOneRow2(node.left, val, depth, level);
    	addOneRow2(node.right, val, depth, level);
    }
}
